๐Ÿ‘ฉโ€๐Ÿ’ป 76503. ๋ชจ๋‘ 0์œผ๋กœ ๋งŒ๋“ค๊ธฐ

@Seongukbaek Posted August 04, 2022 ยท Updated August 04, 2022 ยท 2 min read

๋ฌธ์ œ

Programmers - ๋ชจ๋‘ 0์œผ๋กœ ๋งŒ๋“ค๊ธฐ

๐Ÿ“ Logic

private long dfs(int node) { visited[node] = true; // ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค๋ฉด ํƒ์ƒ‰ for (int i = 0; i < adjList[node].size(); i++) { int cur = adjList[node].get(i); if (!visited[cur]) values[node] += dfs(cur); } // ๋Ÿฐํƒ€์ž„ ์—๋Ÿฌ ์›์ธ // for (int n : adjList[node]) // if (!visited[n]) // values[node] += dfs(n); long value = values[node]; answer += Math.abs(value); return value; }
  • ๋ฆฌํ”„ ๋…ธ๋“œ๋ถ€ํ„ฐ 0์œผ๋กœ ๋งŒ๋“ ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Solution { private ArrayList<Integer>[] adjList; private int size; private long answer = 0; private long[] values; private boolean[] visited; public long solution(int[] a, int[][] edges) { size = a.length; values = new long[size]; visited = new boolean[size]; adjList = new ArrayList[size]; if (init(a) != 0) return -1; for (int[] edge : edges) { int n1 = edge[0]; int n2 = edge[1]; adjList[n1].add(n2); adjList[n2].add(n1); } dfs(0); return answer; } private int init(int[] a) { int sum = 0; for (int i = 0; i < size; i++) { sum += a[i]; values[i] = a[i]; adjList[i] = new ArrayList<>(); } return sum; } private long dfs(int node) { visited[node] = true; // ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค๋ฉด ํƒ์ƒ‰ for (int i = 0; i < adjList[node].size(); i++) { int cur = adjList[node].get(i); if (!visited[cur]) values[node] += dfs(cur); } // ๋Ÿฐํƒ€์ž„ ์—๋Ÿฌ ์›์ธ // for (int n : adjList[node]) // if (!visited[n]) // values[node] += dfs(n); long value = values[node]; answer += Math.abs(value); return value; } }

โœ๏ธ Review

  • ํŠธ๋ฆฌ๋ฅผ ๊ทธ๋ ค๋‘๊ณ  ๋ฆฌํ”„ ๋…ธ๋“œ๋ถ€ํ„ฐ ๋ณด๋‹ค๋ณด๋‹ˆ ์•„์ด๋””์–ด๋Š” ์‰ฝ๊ฒŒ ์žก์„ ์ˆ˜ ์žˆ์—ˆ๋‹ค.
  • ๊ณ„์† 6, 7, 8์—์„œ ๋Ÿฐํƒ€์ž„ ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋‹ค ....

    • Enhanced for๋ฌธ ์‚ฌ์šฉ์œผ๋กœ ์ธํ•œ ๋Ÿฐํƒ€์ž„ ์—๋Ÿฌ์˜€๋‹ค๋Š” ๊ฑธ ์•Œ๊ฒŒ ๋๊ณ .. ์ •๋ฆฌํ•ด์•ผ๊ฒ ๋‹ค.
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€